{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Egg Drop With 2 Eggs and N Floors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: twoEggDrop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #鸡蛋掉落-两枚鸡蛋"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你 <strong>2&nbsp;枚相同 </strong>的鸡蛋，和一栋从第 <code>1</code>&nbsp;层到第 <code>n</code> 层共有 <code>n</code> 层楼的建筑。</p>\n",
    "\n",
    "<p>已知存在楼层 <code>f</code> ，满足&nbsp;<code>0 &lt;= f &lt;= n</code> ，任何从 <strong>高于 </strong><code>f</code> 的楼层落下的鸡蛋都<strong> 会碎 </strong>，从 <strong><code>f</code> 楼层或比它低 </strong>的楼层落下的鸡蛋都 <strong>不会碎 </strong>。</p>\n",
    "\n",
    "<p>每次操作，你可以取一枚<strong> 没有碎</strong> 的鸡蛋并把它从任一楼层 <code>x</code> 扔下（满足&nbsp;<code>1 &lt;= x &lt;= n</code>）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中<strong> 重复使用 </strong>这枚鸡蛋。</p>\n",
    "\n",
    "<p>请你计算并返回要确定 <code>f</code> <strong>确切的值 </strong>的 <strong>最小操作次数</strong> 是多少？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚从 2 楼扔下。\n",
    "如果第一枚鸡蛋碎了，可知 f = 0；\n",
    "如果第二枚鸡蛋碎了，但第一枚没碎，可知 f = 1；\n",
    "否则，当两个鸡蛋都没碎时，可知 f = 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 100\n",
    "<strong>输出：</strong>14\n",
    "<strong>解释：\n",
    "</strong>一种最优的策略是：\n",
    "- 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。\n",
    "- 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。\n",
    "- 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。\n",
    "不管结果如何，最多需要扔 14 次来确定 f 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [egg-drop-with-2-eggs-and-n-floors](https://leetcode.cn/problems/egg-drop-with-2-eggs-and-n-floors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [egg-drop-with-2-eggs-and-n-floors](https://leetcode.cn/problems/egg-drop-with-2-eggs-and-n-floors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '100']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        #（x + 1) * x == 2 * n\n",
    "        # x**2 + x == 2 * n\n",
    "        # x**2 + x - 2 * n = 0\n",
    "        # \n",
    "        step = (-1 + sqrt(1 + 8 * n)) / 2\n",
    "        return ceil(step)\n",
    "        cur_floor = 0\n",
    "        ans = 0\n",
    "        while cur_floor <= n:\n",
    "            pass\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        return math.ceil( ((1+8*n)**0.5 - 1)/2 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        return ceil((sqrt(8 * n + 1) - 1) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        return math.ceil((math.sqrt(8*n) - 1) / 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        dp = [[float(\"inf\")]*(n+1) for _ in range(2)]\n",
    "        for i in range(1, n+1):\n",
    "            dp[0][i] = i\n",
    "        dp[0][0], dp[1][0] = 0, 0\n",
    "        for j in range(1, n+1):\n",
    "            for k in range(1, j+1):\n",
    "                dp[1][j] = min(dp[1][j], max(dp[0][k-1]+1, dp[1][j-k]+1))\n",
    "        print(dp[1][n])\n",
    "        return dp[1][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        return math.ceil(2*math.sqrt(n/2)-0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        dp = [n+1]*(n+1)\n",
    "        dp[0]=0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,i+1):\n",
    "                dp[i] = min(dp[i],max(j,dp[i-j]+1))\n",
    "        return dp[n]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        s=0\n",
    "        a=0\n",
    "        while s<n:\n",
    "            a+=1\n",
    "            s+=a\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "\n",
    "        # 设第一次在第K层扔，第二次再向上K-1层，第三次再向上K-2，直到再上去1层刚好得到n\n",
    "        # 所以K + K -1 + K-2 + ... + 2 + 1,总共是k次， 和为n\n",
    "        # 从最上面往下走，倒数第一次是第n层 然后是n-1 然后是n-1-2\n",
    "        c = 0\n",
    "        t = 0\n",
    "        while c < n:\n",
    "            n -= t\n",
    "            t += 1\n",
    "            c += 1\n",
    "            # print(n)\n",
    "        return c\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        dp = [0]\n",
    "        for j in range(1, n + 1):\n",
    "            dp.append(min([max(k, dp[j - k] + 1) for k in range(1, j + 1)]))\n",
    "        return dp[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        return round((n*2)**0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(3)]\n",
    "        m = 0  # 操作次数\n",
    "        while dp[2][m] < n:\n",
    "            m += 1\n",
    "            for k in range(1, 3):\n",
    "                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1\n",
    "\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        dp = [[0] * (n + 1), [0] * (n + 1)]\n",
    "        for j in range(1, n + 1):\n",
    "            dp[0][j] = j\n",
    "            dp[1][j] = min([max(dp[0][k - 1], dp[1][j - k]) for k in range(1, j + 1)]) + 1\n",
    "        return dp[-1][-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        '''\n",
    "        dp[i][0]表示只有一颗蛋去检测i层楼需要的最小次数；\n",
    "        dp[i][1]表示有两颗蛋去检测i层楼需要的最小次数。\n",
    "        '''\n",
    "        dp = [[float('inf')]*2 for _ in range(n+1)]\n",
    "        dp[0] = [0, 0]\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = i\n",
    "            for k in range(1,i+1):\n",
    "                dp[i][1] = min(dp[i][1], max(dp[k-1][0], dp[i-k][1])+1)\n",
    "        return dp[n][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        dp = [[float('inf')]*2 for _ in range(n+1)]\n",
    "        dp[0] = [0,0]\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = i\n",
    "            for k in range(1, i+1):\n",
    "                dp[i][1] = min(dp[i][1], max(dp[k-1][0], dp[i-k][1])+1)\n",
    "        return dp[n][1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        dp = [[float(inf)] * 2 for _ in range(n+1)]\n",
    "        dp[0] = [0,0]\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = i\n",
    "            for k in range(1,i+1):\n",
    "                dp[i][1] = min(dp[i][1], max(dp[k-1][0], dp[i-k][1])+1)\n",
    "        return dp[n][1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # dp\n",
    "    # O(n^2) O(n)\n",
    "    # https://leetcode.cn/problems/egg-drop-with-2-eggs-and-n-floors/solutions/1/1884-ji-dan-diao-luo-liang-mei-ji-dan-by-9yop/\n",
    "    def twoEggDrop1(self, n: int) -> int:\n",
    "        dp = [[0] * 3 for _ in range(n + 1)]\n",
    "\n",
    "        for j in range(1, 3):\n",
    "            dp[1][j] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][1] = i\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i][2] = float('inf')\n",
    "            for p in range(1, i + 1):\n",
    "                curr = max(dp[p - 1][1], dp[i - p][2]) + 1\n",
    "                dp[i][2] = min(dp[i][2], curr)\n",
    "\n",
    "        return dp[n][2]\n",
    "\n",
    "\n",
    "\n",
    "    # ?\n",
    "    # O(nlogn) O(n)\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        dp = [[0] * 3 for _ in range(n + 1)]\n",
    "\n",
    "        for j in range(1, 3):\n",
    "            dp[1][j] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][1] = i\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            low, high = 1, i\n",
    "\n",
    "            while high - low > 1:\n",
    "                mid = low + (high - low) // 2\n",
    "\n",
    "                if dp[mid - 1][1] <= dp[i - mid][2]:\n",
    "                    low = mid\n",
    "                if dp[mid - 1][1] >= dp[i - mid][2]:\n",
    "                    high = mid\n",
    "\n",
    "            count1 = max(dp[low - 1][1], dp[i - low][2])\n",
    "            count2 = max(dp[high - 1][1], dp[i - high][2])\n",
    "\n",
    "            dp[i][2] = min(count1, count2) + 1\n",
    "\n",
    "        return dp[n][2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def twoEggDrop(self, n: int) -> int:\n",
    "    #     # 1.DP solution\n",
    "    #     # time complexity: O(N^2*K)\n",
    "    #     # space complexity: O(N*K)\n",
    "    #     from functools import lru_cache\n",
    "\n",
    "    #     @lru_cache(None)\n",
    "    #     def dp(i: int, k: int) -> int:\n",
    "    #         if i == 0:\n",
    "    #             return 0\n",
    "    #         if k == 1:\n",
    "    #             return i\n",
    "\n",
    "    #         min_attempts = float(\"inf\")\n",
    "    #         for j in range(1, i + 1):\n",
    "    #             # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "    #             # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "    #             broken = dp(j - 1, k - 1)\n",
    "    #             not_broken = dp(i - j, k)\n",
    "\n",
    "    #             # chose the worst case\n",
    "    #             current_attempts = 1 + max(broken, not_broken)\n",
    "    #             min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "    #         return min_attempts\n",
    "\n",
    "    #     return dp(n, 2)\n",
    "\n",
    "    # def twoEggDrop(self, n: int) -> int:\n",
    "    #     # 2.DP solution with binary search optimization\n",
    "    #     # time complexity: O(N^2*K)\n",
    "    #     # space complexity: O(N*K)\n",
    "    #     from functools import lru_cache\n",
    "\n",
    "    #     @lru_cache(None)\n",
    "    #     def dp(i: int, k: int) -> int:\n",
    "    #         if i == 0:\n",
    "    #             return 0\n",
    "    #         if k == 1:\n",
    "    #             return i\n",
    "\n",
    "    #         min_attempts = float(\"inf\")\n",
    "    #         l, r = 1, i + 1\n",
    "    #         while l <= r:\n",
    "    #             # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "    #             # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "\n",
    "    #             j = (l + r) >> 1\n",
    "    #             broken = dp(j - 1, k - 1)\n",
    "    #             not_broken = dp(i - j, k)\n",
    "\n",
    "    #             # chose the worst case\n",
    "    #             current_attempts = 1 + max(broken, not_broken)\n",
    "    #             min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "    #             if broken < not_broken:\n",
    "    #                 l = j + 1\n",
    "    #             else:\n",
    "    #                 r = j - 1\n",
    "    #         return min_attempts\n",
    "\n",
    "    #     return dp(n, 2)\n",
    "\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        # 3.Other DP solution\n",
    "        # time complexity: O(K*logN)\n",
    "        # space complexity: O(N*K)\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache\n",
    "        def dp(i: int, k: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return i\n",
    "\n",
    "            return 1 + dp(i - 1, k - 1) + dp(i - 1, k)\n",
    "\n",
    "        for m in range(1, n + 1):\n",
    "            if dp(m, 2) >= n:\n",
    "                return m\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        global memo\n",
    "        # memo[(k,i)]: number of operations when start operations on i levels with k eggs remaining \n",
    "        memo = {}\n",
    "        # dp(k,i) = min(res, max(oprations after this level) + 1)\n",
    "        return dp(2,n)\n",
    "\n",
    "memo = {}\n",
    "def dp(k: int, n: int) -> int:\n",
    "    global memo \n",
    "    if (k,n) in memo:\n",
    "        return memo[(k,n)]\n",
    "    cur = (k,n)\n",
    "    # base cases \n",
    "    if k == 1:\n",
    "        # linearly scanning with only 1 egg \n",
    "        memo[cur] = n \n",
    "        return n \n",
    "    if n == 0:\n",
    "        # 0 floors need to be tested, no need to drop\n",
    "        memo[cur] = 0 \n",
    "        return 0 \n",
    "    \n",
    "    # state transition \n",
    "    res = float('inf')\n",
    "    for i in range(1,n+1):\n",
    "        # maximum of the 2 options,egg broken or unbroken\n",
    "        # broken, search below: dp(k-1,i-1) + 1\n",
    "        # unbroken, search above: dp(k,n-i) + 1 \n",
    "        res = min(res,max(dp(k-1,i-1),dp(k,n-i)) + 1)\n",
    "    # save the result\n",
    "    memo[cur] = res \n",
    "    return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        \n",
    "\n",
    "        def dfs(i,s):\n",
    "            if i==0:\n",
    "                return s\n",
    "            s=s+i\n",
    "            return dfs(i-1,s)\n",
    "\n",
    "        l=int(n**0.5)\n",
    "        r=n\n",
    "        while l+1<r:\n",
    "            mid=(l+r)//2\n",
    "            if dfs(mid,0)>=n:\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid\n",
    "        \n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "@lru_cache(None)\n",
    "def search(n_floor, n_egg):\n",
    "    if n_floor == 1:\n",
    "        return 1\n",
    "    if n_egg == 1:\n",
    "        return n_floor\n",
    "    \n",
    "    rnt = n_floor\n",
    "    for i_floor in range(1, n_floor+1):\n",
    "        # broken\n",
    "        broken = search(i_floor-1, 1)\n",
    "\n",
    "        # not broken\n",
    "        not_broken = search(n_floor-i_floor, 2)\n",
    "\n",
    "        rnt = min(rnt, max(broken, not_broken) + 1)\n",
    "    \n",
    "    print(n_floor, n_egg, rnt)\n",
    "    return rnt\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        return search(n, 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(n):\n",
    "            if n < 3:\n",
    "                return n\n",
    "            m = n\n",
    "            i = 2\n",
    "            while i < m:\n",
    "                m = min(m, max(i, 1 + f(n - i)))\n",
    "                i += 1\n",
    "            return m\n",
    "        \n",
    "        return f(n)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(n):\n",
    "            if n < 3:\n",
    "                return n\n",
    "            ans = n\n",
    "            for i in range(1, n // 2 + 2):\n",
    "                ans = min(ans, max(i, 1 + dp(n-i)))\n",
    "            return ans\n",
    "        return dp(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        \n",
    "\n",
    "        def dfs(i,s):\n",
    "            if i==0:\n",
    "                return s\n",
    "            s=s+i\n",
    "            return dfs(i-1,s)\n",
    "\n",
    "        l=int(n**0.5)\n",
    "        r=n\n",
    "        while l+1<r:\n",
    "            mid=(l+r)//2\n",
    "            if dfs(mid,0)>=n:\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid\n",
    "        \n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "memorandum = dict()\n",
    "class Solution:\n",
    "\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        return self.dropEggs(2,n)\n",
    "\n",
    "        \n",
    "    def dropEggs(self, K: int, N: int) -> int:\n",
    "        \"\"\"\n",
    "        # K levels with n eggs\n",
    "        def dp(K, N):\n",
    "            int res\n",
    "            for 1 <= i <= N:\n",
    "                res = min(res, drop an egg in level-i )\n",
    "            return res\n",
    "\n",
    "\n",
    "        status transfer equation for dropping an egg in level-i:\n",
    "            if the egg was broken:\n",
    "                the number of eggs minus one, and the searching region was narrowed from [1,N] to [1, i-1];\n",
    "            if the egg was unbroken:\n",
    "                the number of eggs was unchanged, and the searching region was narrowed from [1,N] to [i+1,N]\n",
    "            dp = min(res, max())\n",
    "        :param k:\n",
    "        :type k:\n",
    "        :return:\n",
    "        :rtype:\n",
    "        \"\"\"\n",
    "\n",
    "        def dp(K: int, N: int) -> int:\n",
    "            _ = (K, N)\n",
    "            if memorandum.get(_):\n",
    "                return memorandum[_]\n",
    "            if K == 1:\n",
    "                memorandum[_] = N\n",
    "                return N\n",
    "            if N == 0:\n",
    "                memorandum[_] = 0\n",
    "                return memorandum[_]\n",
    "            res = float('INF')\n",
    "            for i in range(1, N + 1):\n",
    "                isBroken = memorandum.get((K - 1, i - 1))\n",
    "                if not isBroken:\n",
    "                    isBroken = dp(K - 1, i - 1)\n",
    "                    memorandum[(K - 1, i - 1)] = isBroken\n",
    "                isUnbroken = memorandum.get((K, N - i))\n",
    "                if not isUnbroken:\n",
    "                    isUnbroken = dp(K, N - i)\n",
    "                    memorandum[(K, N - i)] = isUnbroken\n",
    "                res = min(res, max(isBroken, isUnbroken) + 1)\n",
    "            memorandum[_] = res\n",
    "            return res\n",
    "\n",
    "        return dp(K, N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @cache\n",
    "        def back(l,r):\n",
    "            res = r-l\n",
    "            for i in range(l+1,r):\n",
    "                res = min(res,1+max((i-l),back(i+1,r)))\n",
    "            return res\n",
    "        return back(0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @cache\n",
    "        def back(l,r):\n",
    "            res = r-l\n",
    "            for i in range(l+1,r):\n",
    "                res = min(res,1+max((i-l),back(i+1,r)))\n",
    "            return res\n",
    "        return back(0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        memo = {}\n",
    "        def dp(k, n):\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            \n",
    "            if (k, n) in memo:\n",
    "                return memo[(k, n)]\n",
    "        \n",
    "            res = float('inf')\n",
    "            for i in range(1, n+1):\n",
    "                res = min(res, max(dp(k, n - i),\n",
    "                                    dp(k-1, i-1))+1)\n",
    "            memo[(k, n)] = res\n",
    "            return res\n",
    "\n",
    "        return dp(2, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superEggDrop(self, k: int, n: int) -> int:\n",
    "        memo = dict()\n",
    "        def dp(k: int, n: int):\n",
    "            if(k==1):\n",
    "                return n\n",
    "            if(n==0):\n",
    "                return 0\n",
    "            if((k,n) in memo):\n",
    "                return memo[(k,n)]\n",
    "            \n",
    "            res = n\n",
    "            for i in range(1,n+1):\n",
    "                res = min(res,max(dp(k,n-i),dp(k-1,i-1))+1)\n",
    "            memo[(k,n ) ]=res\n",
    "            return res\n",
    "        return dp(k,n)\n",
    "\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        return self.superEggDrop(2,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        def dfs(k, n):\n",
    "            # 当前有k个鸡蛋，n层楼房。在最坏情况下，返回所需的最小操作数\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            if (k,n) in memo:\n",
    "                return memo[(k,n)]\n",
    "\n",
    "            # 做选择\n",
    "            res = float('inf')\n",
    "            # for i in range(1, n+1):\n",
    "            #     # 从第i层扔下：鸡蛋碎了，鸡蛋没碎\n",
    "            #     # 鸡蛋碎了，向下搜索：dfs(k-1, i-1)\n",
    "            #     # 鸡蛋没碎，向上搜索：dfs(k, n-i)\n",
    "            #     res = min(res, max(dfs(k-1, i-1), dfs(k, n-i))+1)\n",
    "            \n",
    "            # 因为递推函数是单调，可以用二分法来优化线性搜索的复杂度\n",
    "            lo, hi = 1, n\n",
    "            while lo <= hi:\n",
    "                mid = (lo+hi)//2\n",
    "                broken = dfs(k-1, mid-1)\n",
    "                not_broken = dfs(k, n-mid)\n",
    "                if broken > not_broken:\n",
    "                    hi = mid-1\n",
    "                    res = min(res, broken+1)\n",
    "                else:\n",
    "                    lo = mid+1\n",
    "                    res = min(res, not_broken+1)\n",
    "            \n",
    "            memo[(k,n)] = res\n",
    "            return res\n",
    "\n",
    "        memo = {}\n",
    "        return dfs(2, n)\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        mem = [[-1] * 3 for _ in range(n + 1)]\n",
    "\n",
    "        def dp(i, j) -> int:\n",
    "            if mem[i][j] != -1:\n",
    "                return mem[i][j]\n",
    "            nonlocal n\n",
    "            if i == 0:\n",
    "                mem[i][j] = 0\n",
    "                return 0\n",
    "            if j == 1:\n",
    "                mem[i][j] = i\n",
    "                return i\n",
    "            res = 1000\n",
    "            for k in range(1, i + 1):\n",
    "                res = min(res, 1 + max(dp(k - 1, j - 1), dp(i - k, j)))\n",
    "            mem[i][j] = res\n",
    "            return res\n",
    "\n",
    "        return dp(n, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        dick11 = {}\n",
    "\n",
    "        def dp(n, k) -> int:\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            res = 100000000\n",
    "            if (n, k) in dick11:\n",
    "                return dick11[(n, k)]\n",
    "            for i in range(1, n + 1):\n",
    "                temp = max(dp(n - i, k), dp(i - 1, k - 1)) + 1\n",
    "                res = min(temp, res)\n",
    "            dick11[(n, k)] = res\n",
    "            return dick11[(n, k)]\n",
    "\n",
    "        return dp(n, 2)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        mem = defaultdict()\n",
    "\n",
    "        def dp (k:int, n:int) -> int:\n",
    "            if (k,n) not in mem:\n",
    "                if n == 0:\n",
    "                    return 0\n",
    "                elif k == 1:\n",
    "                    return n\n",
    "                else:\n",
    "                    # 因为顺序超时，改为二分查找\n",
    "                    lo, hi = 1, n\n",
    "                    ans = sys.maxsize\n",
    "                    while lo + 1 < hi:\n",
    "                        x = (lo + hi) // 2\n",
    "                        t1 = dp(k-1, x-1)\n",
    "                        t2 = dp(k,n-x)\n",
    "                        if t1 < t2:\n",
    "                            lo = x\n",
    "                        elif t1 > t2:\n",
    "                            hi = x \n",
    "                        else: \n",
    "                            lo = hi = x\n",
    "\n",
    "                    for x in (lo, hi):\n",
    "                        #print(x)\n",
    "                        ans = 1 + min(ans,max(dp(k - 1, x - 1), dp(k, n - x)))\n",
    "                    mem[(k,n)] = ans\n",
    "            return mem[(k,n)]\n",
    "        return dp(2,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        def dfs(k, n):\n",
    "            # 表示有k个鸡蛋，n层楼的状态下，最坏情况下找到f层楼所需的最小操作数\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            if (k, n) in memo:\n",
    "                return memo[(k,n)]\n",
    "            \n",
    "\n",
    "            # 做选择\n",
    "            res = float('inf')\n",
    "            # for i in range(1, n+1):\n",
    "            #     # 选择在第i层扔鸡蛋，存在两种可能\n",
    "            #     # 鸡蛋碎 dfs(k-1, i-1)\n",
    "            #     # 鸡蛋没碎 dfs(k, n-i)\n",
    "            #     res = min(res, max(dfs(k-1, i-1), dfs(k, n-i))+1)\n",
    "            \n",
    "            # 用二分优化线性搜索的时间复杂度，本质上相当于找最小值\n",
    "            lo, hi = 1, n\n",
    "            while lo <= hi:\n",
    "                # 从中间楼层开始搜索\n",
    "                mid = (lo+hi)//2\n",
    "                broken = dfs(k-1, n-mid)#搜mid上方的楼层\n",
    "                not_broken = dfs(k, mid-1)#搜mid下方的楼层\n",
    "\n",
    "                if broken > not_broken:#mid在最小值左侧\n",
    "                    lo = mid+1\n",
    "                    res = min(res, broken+1)\n",
    "                else:\n",
    "                    hi = mid-1\n",
    "                    res = min(res, not_broken+1)\n",
    "\n",
    "            memo[(k,n)] = res\n",
    "            return res\n",
    "        \n",
    "        memo = {}\n",
    "        return dfs(2, n)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j: return 0\n",
    "            res = inf\n",
    "            for k in range(i, j + 1):\n",
    "                res = min(res, max(k - i, dfs(k + 1, j)) + 1)\n",
    "            return res\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        memo = {}\n",
    "        \n",
    "        def dp(K,N):\n",
    "            if K == 1:return N\n",
    "            if N == 0:return 0\n",
    "            if (K,N) in memo:\n",
    "                return memo[(K,N)]\n",
    "            res = float('INF')\n",
    "            for i in range(1,N+1):\n",
    "                res = min(res,max(dp(K-1,i-1),dp(K,N-i))+1)\n",
    "            memo[(K,N)] = res\n",
    "            return res\n",
    "        return dp(2,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        '''\n",
    "        dp(k, n)\n",
    "\n",
    "        dp(k, n) = min(         # 最小次数\n",
    "            dp(k, n),\n",
    "            max(                # 最坏情况\n",
    "                dp(k-1, i-1),     # broken\n",
    "                dp(k, n-i),       # non-broken\n",
    "            ) + 1\n",
    "        )\n",
    "\n",
    "        k = 1, dp(k, n) = n\n",
    "        k = 0, dp(k, n) = 0\n",
    "        n = 1, dp(k, n) = 1\n",
    "        '''\n",
    "        k = 2\n",
    "        memo = {}\n",
    "        def dp(k, n):\n",
    "            if k == 1 or n == 1:\n",
    "                return n\n",
    "            if k == 0 or n == 0:\n",
    "                return 0\n",
    "            if (k, n) in memo:\n",
    "                return memo[(k, n)]\n",
    "            res = n\n",
    "            for i in range(1, n+1):\n",
    "                res = min(         # 最小次数\n",
    "                    res,\n",
    "                    max(                # 最坏情况\n",
    "                        dp(k-1, i-1),     # broken\n",
    "                        dp(k, n-i),       # non-broken\n",
    "                    ) + 1\n",
    "                )\n",
    "            memo[(k, n)] = res\n",
    "            return res\n",
    "        return dp(k, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def twoEggDrop(self, n: int) -> int:\n",
    "    #     # 1.DP solution\n",
    "    #     # time complexity: O(N^2*K)\n",
    "    #     # space complexity: O(N*K)\n",
    "    #     from functools import lru_cache\n",
    "\n",
    "    #     @lru_cache(None)\n",
    "    #     def dp(i: int, k: int) -> int:\n",
    "    #         if i == 0:\n",
    "    #             return 0\n",
    "    #         if k == 1:\n",
    "    #             return i\n",
    "\n",
    "    #         min_attempts = float(\"inf\")\n",
    "    #         for j in range(1, i + 1):\n",
    "    #             # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "    #             # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "    #             broken = dp(j - 1, k - 1)\n",
    "    #             not_broken = dp(i - j, k)\n",
    "\n",
    "    #             # chose the worst case\n",
    "    #             current_attempts = 1 + max(broken, not_broken)\n",
    "    #             min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "    #         return min_attempts\n",
    "\n",
    "    #     return dp(n, 2)\n",
    "\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        # 2.DP solution with binary search optimization\n",
    "        # time complexity: O(N^2*K)\n",
    "        # space complexity: O(N*K)\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i: int, k: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return i\n",
    "\n",
    "            min_attempts = float(\"inf\")\n",
    "            l, r = 1, i + 1\n",
    "            while l <= r:\n",
    "                # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "                # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "\n",
    "                j = (l + r) >> 1\n",
    "                broken = dp(j - 1, k - 1)\n",
    "                not_broken = dp(i - j, k)\n",
    "\n",
    "                # chose the worst case\n",
    "                current_attempts = 1 + max(broken, not_broken)\n",
    "                min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "                if broken < not_broken:\n",
    "                    l = j + 1\n",
    "                else:\n",
    "                    r = j - 1\n",
    "            return min_attempts\n",
    "\n",
    "        return dp(n, 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(k, n):\n",
    "            if k == 1:\n",
    "                if n > 0:\n",
    "                    return n\n",
    "                else:\n",
    "                    return 0\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            mi = float('inf')\n",
    "            for i in range(1, n + 1):\n",
    "                mi = min(mi, 1 + max(dp(k - 1, i), dp(k, n - i - 1)))\n",
    "            return mi\n",
    "\n",
    "        return dp(2, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def twoEggDrop(self, n: int) -> int:\n",
    "    #     # 1.DP solution\n",
    "    #     # time complexity: O(N^2*K)\n",
    "    #     # space complexity: O(N*K)\n",
    "    #     from functools import lru_cache\n",
    "\n",
    "    #     @lru_cache(None)\n",
    "    #     def dp(i: int, k: int) -> int:\n",
    "    #         if i == 0:\n",
    "    #             return 0\n",
    "    #         if k == 1:\n",
    "    #             return i\n",
    "\n",
    "    #         min_attempts = float(\"inf\")\n",
    "    #         for j in range(1, i + 1):\n",
    "    #             # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "    #             # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "    #             broken = dp(j - 1, k - 1)\n",
    "    #             not_broken = dp(i - j, k)\n",
    "\n",
    "    #             # chose the worst case\n",
    "    #             current_attempts = 1 + max(broken, not_broken)\n",
    "    #             min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "    #         return min_attempts\n",
    "\n",
    "    #     return dp(n, 2)\n",
    "\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        # 2.DP solution with binary search optimization\n",
    "        # time complexity: O(N^2*K)\n",
    "        # space complexity: O(N*K)\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i: int, k: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return i\n",
    "\n",
    "            min_attempts = float(\"inf\")\n",
    "            l, r = 1, i + 1\n",
    "            while l <= r:\n",
    "                # for j in range(1, i + 1):\n",
    "                # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "                # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "\n",
    "                j = (l + r) // 2\n",
    "                broken = dp(j - 1, k - 1)\n",
    "                not_broken = dp(i - j, k)\n",
    "\n",
    "                # chose the worst case\n",
    "                current_attempts = 1 + max(broken, not_broken)\n",
    "                min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "                if broken < not_broken:\n",
    "                    l = j + 1\n",
    "                else:\n",
    "                    r = j - 1\n",
    "            return min_attempts\n",
    "\n",
    "        return dp(n, 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        memo = [float('inf')] * (n + 1)\n",
    "        def dp(n):\n",
    "            if n == 0: return 0\n",
    "            if memo[n] != float('inf'): return memo[n]\n",
    "            for i in range(1, n + 1):\n",
    "                memo[n] = min(\n",
    "                    memo[n],\n",
    "                    max(\n",
    "                        i,\n",
    "                        dp(n - i) + 1\n",
    "                    )\n",
    "                )\n",
    "            return memo[n]\n",
    "        return dp(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(k, n):\n",
    "            if k == 1:\n",
    "                if n > 0:\n",
    "                    return n\n",
    "                else:\n",
    "                    return 0\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            mi = float('inf')\n",
    "            for i in range(1, n):\n",
    "                mi = min(mi, 1 + max(dp(k - 1, i), dp(k, n - i - 1)))\n",
    "            return mi\n",
    "\n",
    "        return dp(2, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def twoEggDrop(self, n: int) -> int:\n",
    "    #     # 1.DP solution\n",
    "    #     # time complexity: O(N^2*K)\n",
    "    #     # space complexity: O(N*K)\n",
    "    #     from functools import lru_cache\n",
    "\n",
    "    #     @lru_cache(None)\n",
    "    #     def dp(i: int, k: int) -> int:\n",
    "    #         if i == 0:\n",
    "    #             return 0\n",
    "    #         if k == 1:\n",
    "    #             return i\n",
    "\n",
    "    #         min_attempts = float(\"inf\")\n",
    "    #         for j in range(1, i + 1):\n",
    "    #             # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "    #             # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "    #             broken = dp(j - 1, k - 1)\n",
    "    #             not_broken = dp(i - j, k)\n",
    "\n",
    "    #             # chose the worst case\n",
    "    #             current_attempts = 1 + max(broken, not_broken)\n",
    "    #             min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "    #         return min_attempts\n",
    "\n",
    "    #     return dp(n, 2)\n",
    "\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        # 2.DP solution with binary search optimization\n",
    "        # time complexity: O(N^2*K)\n",
    "        # space complexity: O(N*K)\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i: int, k: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return i\n",
    "\n",
    "            min_attempts = float(\"inf\")\n",
    "            l, r = 1, i + 1\n",
    "            while l <= r:\n",
    "                # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "                # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "\n",
    "                j = (l + r) >> 1\n",
    "                broken = dp(j - 1, k - 1)\n",
    "                not_broken = dp(i - j, k)\n",
    "\n",
    "                # chose the worst case\n",
    "                current_attempts = 1 + max(broken, not_broken)\n",
    "                min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "                if broken < not_broken:\n",
    "                    l = j + 1\n",
    "                else:\n",
    "                    r = j - 1\n",
    "            return min_attempts\n",
    "\n",
    "        return dp(n, 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(k, n):\n",
    "            if k == 1:\n",
    "                if n > 0:\n",
    "                    return n\n",
    "                else:\n",
    "                    return 0\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            mi = float('inf')\n",
    "            for i in range(1, n + 1):\n",
    "                mi = min(mi, 1 + max(dp(k - 1, i), dp(k, n - i - 1)))\n",
    "            return mi\n",
    "\n",
    "        return dp(2, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        ma={}\n",
    "        def fun(k,n):\n",
    "            if (k,n) in ma:\n",
    "                return ma[(k,n)]\n",
    "            if k==1:\n",
    "                ma[(k,n)]=n\n",
    "                return n\n",
    "            if n==0:\n",
    "                ma[(k,n)]=0\n",
    "                return 0\n",
    "            re=n+1\n",
    "            for i in range(1,n+1):\n",
    "                re=min(re,max(fun(k-1,i-1),fun(k,n-i))+1)\n",
    "            ma[(k,n)]=re\n",
    "            return ma[(k,n)]\n",
    "        return fun(2,n)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(K,N):                 #返回K个鸡蛋N层楼(状态下的最优结果)\n",
    "            if K==1: return N        #1个鸡蛋只能线性扫描\n",
    "            if N==0: return 0        #层数已经为0，不用仍鸡蛋\n",
    "            ans=1000000000\n",
    "            for i in range(1,N+1):   #选择从第i层楼扔下鸡蛋\n",
    "                ans=min(ans,max(dp(K-1,i-1),dp(K,N-i))+1)\n",
    "            return ans \n",
    "        \n",
    "        return dp(2,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(n, k):\n",
    "            if k == 1: return n\n",
    "            if n < 3: return n\n",
    "            res = inf\n",
    "            for i in range(1, n + 1):\n",
    "                tmp = max(f(n - i, 2), f(i - 1, 1)) + 1\n",
    "                res = min(res, tmp)\n",
    "            return res \n",
    "        return f(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        ans = [[float('inf') for _ in range(n+1)] for _ in range(2)]\n",
    "        for i in range(n+1):\n",
    "            ans[0][i] = i  # 当只有一个鸡蛋时，对于任意的n层楼，至少需要扔n次\n",
    "\n",
    "        def dp(k, n):\n",
    "            if ans[k][n] != float('inf'):\n",
    "                return ans[k][n]\n",
    "            if n == 0: return 0 \n",
    "            res = float('inf')\n",
    "            for i in range(1, n+1):\n",
    "                res = min(res, max(dp(k, n-i), dp(k-1, i-1)) + 1)\n",
    "            ans[k][n] = res\n",
    "            return res\n",
    "        \n",
    "        return dp(1, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        # 举一反三，n是楼层数，k是鸡蛋个数\n",
    "        k = 2\n",
    "        memo = [[0] * (k + 1) for _ in range(0, n + 1)]\n",
    "\n",
    "        def ans(n, k):\n",
    "            # n层楼\n",
    "            # k个鸡蛋\n",
    "            if n == 1:\n",
    "                return 1\n",
    "\n",
    "            elif k == 1:\n",
    "                return n+1\n",
    "\n",
    "            if memo[n][k] != 0:\n",
    "                return memo[n][k]\n",
    "\n",
    "            else:\n",
    "                res = float(\"inf\")\n",
    "\n",
    "                for i in range(1, n + 1):\n",
    "                    res = min(res, max(ans(i-1,k-1), ans(n-i,k) + 1))\n",
    "\n",
    "                memo[n][k] = res\n",
    "\n",
    "                return res\n",
    "\n",
    "\n",
    "        return ans(n=n,k=2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        \n",
    "        # 定义k个鸡蛋 验证n个楼层\n",
    "        @cache\n",
    "        def dp(n:int ,k:int) -> int:\n",
    "            if n == 0: return 0\n",
    "            if k == 1: return n\n",
    "            res = float('inf')\n",
    "            for i in range(1,n+1):\n",
    "                res = min(res,max(dp(i-1,k-1),dp(n-i,k)) + 1)\n",
    "            return res\n",
    "        return dp(n,2)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(K,N):                 #返回K个鸡蛋N层楼(状态下的最优结果)\n",
    "            if K==1: return N        #1个鸡蛋只能线性扫描\n",
    "            if N==0: return 0        #层数已经为0，不用仍鸡蛋\n",
    "            ans=1000000000\n",
    "            for i in range(1,N+1):   #选择从第i层楼扔下鸡蛋\n",
    "                ans=min(ans,max(dp(K-1,i-1),dp(K,N-i))+1)\n",
    "            return ans \n",
    "        \n",
    "        return dp(2,n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(x,y):\n",
    "            if x==1:\n",
    "                return y\n",
    "            \n",
    "            if y==0:\n",
    "                return 0\n",
    "            \n",
    "            res=n\n",
    "            for i in range(1,y+1):\n",
    "                temp=max(dp(x-1,i-1),dp(x,y-i))+1\n",
    "                res=min(res,temp)\n",
    "\n",
    "            return res\n",
    "        \n",
    "        return dp(2,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(eggs, floors) -> int:\n",
    "            if not floors:\n",
    "                return 0\n",
    "            if eggs == 1 or floors == 1:\n",
    "                return floors\n",
    "            ans = float('inf')\n",
    "            for f in range(1, floors):\n",
    "                ans = min(ans, max(dfs(eggs - 1, f - 1), dfs(eggs, floors - f)) + 1)\n",
    "            return ans\n",
    "        return dfs(2, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(n: int, eggs: int) -> int:\n",
    "            if eggs == 1:\n",
    "                return n\n",
    "            if n <= 2:\n",
    "                return n\n",
    "\n",
    "            res = float('inf')\n",
    "            for i in range(1, n):\n",
    "                res = min(res, max(dfs(i - 1, eggs - 1), dfs(n - i, eggs)) + 1)\n",
    "            return res\n",
    "\n",
    "        return dfs(n, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dp(K, N):\n",
    "            if K == 1:\n",
    "                return N\n",
    "            if N == 0:\n",
    "                return 0\n",
    "            \n",
    "            ans = float('inf')\n",
    "\n",
    "            for i in range(1, N + 1):\n",
    "                ans = min(ans, max(dp(K, N - i), dp(K - 1, i - 1)) + 1)\n",
    "            return ans\n",
    "\n",
    "        return dp(2, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(n, k):\n",
    "            if k == 1: return n\n",
    "            if n == 0 or n == 1: return n\n",
    "            ans = inf\n",
    "            for i in range(1, n+1): \n",
    "                ans = min(max(dp(i-1, k-1), dp(n-i, k)) + 1, ans)\n",
    "            return ans\n",
    "        return dp(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        # 写成记忆化\n",
    "        @cache\n",
    "        def dfs(n, k):\n",
    "            if n == 0:return 0\n",
    "            if k==1:return n\n",
    "\n",
    "            res = inf\n",
    "            for i in range(1, n+1):\n",
    "                # 第k枚鸡蛋，第i层破碎，第i层不破\n",
    "                res = min(res, max(dfs(i-1, k-1), dfs(n-i, k))+1)\n",
    "            return res \n",
    "        \n",
    "        return dfs(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        memo = dict()\n",
    "        def dp(K, N) -> int:\n",
    "            # base case\n",
    "            if K == 1: return N\n",
    "            if N == 0: return 0\n",
    "            # 避免重复计算\n",
    "            if (K, N) in memo:\n",
    "                return memo[(K, N)]\n",
    "\n",
    "            res = float('INF')\n",
    "            # 穷举所有可能的选择\n",
    "            for i in range(1, N + 1):\n",
    "                res = min(res, \n",
    "                        max(\n",
    "                            dp(K, N - i), \n",
    "                            dp(K - 1, i - 1)\n",
    "                        ) + 1\n",
    "                )\n",
    "            # 记入备忘录\n",
    "            memo[(K, N)] = res\n",
    "            return res\n",
    "\n",
    "        return dp(2, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        def dfs(k, n):\n",
    "            # 当前有k个鸡蛋，n层楼房。在最坏情况下，返回所需的最小操作数\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            if (k,n) in memo:\n",
    "                return memo[(k,n)]\n",
    "\n",
    "            # 做选择\n",
    "            res = float('inf')\n",
    "            for i in range(1, n+1):\n",
    "                # 从第i层扔下：鸡蛋碎了，鸡蛋没碎\n",
    "                # 鸡蛋碎了，向下搜索：dfs(k-1, i-1)\n",
    "                # 鸡蛋没碎，向上搜索：dfs(k, n-i)\n",
    "\n",
    "                res = min(res, max(dfs(k-1, i-1), dfs(k, n-i))+1)\n",
    "            memo[(k,n)] = res\n",
    "            return res\n",
    "\n",
    "        memo = {}\n",
    "        return dfs(2, n)\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "\n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        def dp(K, N):\n",
    "\n",
    "            if K == 1: return N\n",
    "            if N == 0: return 0\n",
    "\n",
    "            if (K, N) in memo: return memo[(K, N)]\n",
    "\n",
    "            res = math.inf\n",
    "            for i in range(1, N + 1):\n",
    "                res = min(res,\n",
    "                            max(dp(K - 1, i - 1),     # broken, search downwards\n",
    "                                dp(K, N - i)\n",
    "                            ) + 1\n",
    "                    )\n",
    "            \n",
    "            memo[(K, N)] = res\n",
    "            return res\n",
    "\n",
    "        return dp(2, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        def dfs(k, n):\n",
    "            # 表示有k个鸡蛋，n层楼的状态下，最坏情况下找到f层楼所需的最小操作数\n",
    "            if k == 1:\n",
    "                return n\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            if (k, n) in memo:\n",
    "                return memo[(k,n)]\n",
    "            \n",
    "\n",
    "            # 做选择\n",
    "            res = float('inf')\n",
    "            for i in range(1, n+1):\n",
    "                # 选择在第i层扔鸡蛋，存在两种可能\n",
    "                # 鸡蛋碎 dfs(k-1, i-1)\n",
    "                # 鸡蛋没碎 dfs(k, n-i)\n",
    "                res = min(res, max(dfs(k-1, i-1), dfs(k, n-i))+1)\n",
    "            \n",
    "            # 用二分优化线性搜索的时间复杂度，本质上相当于找最小值\n",
    "            lo, hi = 1, n\n",
    "            while lo <= hi:\n",
    "                # 从中间楼层开始搜索\n",
    "                mid = (lo+hi)//2\n",
    "                broken = dfs(k-1, n-mid)#搜mid上方的楼层\n",
    "                not_broken = dfs(k, mid-1)#搜mid下方的楼层\n",
    "\n",
    "                if broken > not_broken:#mid在最小值左侧\n",
    "                    lo = mid+1\n",
    "                    res = min(res, broken+1)\n",
    "                else:\n",
    "                    hi = mid-1\n",
    "                    res = min(res, not_broken+1)\n",
    "\n",
    "            memo[(k,n)] = res\n",
    "            return res\n",
    "        \n",
    "        memo = {}\n",
    "        return dfs(2, n)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        @lru_cache(10000000)\n",
    "        def helper(n,remain):\n",
    "            # print(n,remain)\n",
    "            if n==0:\n",
    "                return 0\n",
    "            # if n==1:\n",
    "            #     return 1\n",
    "            if remain==1:\n",
    "                return n\n",
    "            ans=n\n",
    "            for i in range(1,n+1):\n",
    "                cur=max(helper(i-1,1),helper(n-i,2))+1\n",
    "                ans=min(ans,cur)\n",
    "            return ans\n",
    "        return helper(n,2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        mem = defaultdict(dict)\n",
    "        def dp(n,k):\n",
    "            if k==1:\n",
    "                return n\n",
    "            if n==0:\n",
    "                return 0\n",
    "            if k in mem[n]:\n",
    "                return mem[n][k]\n",
    "            res = float('inf')\n",
    "            for i in range(1,n+1):\n",
    "                res = min(res, max(dp(n-i,k),dp(i-1,k-1))+1)\n",
    "            mem[n][k] = res\n",
    "            return res\n",
    "        k = 2\n",
    "        dp(n,k)\n",
    "        return mem[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEggDrop(self, n: int) -> int:\n",
    "        # 1.DP solution\n",
    "        # time complexity: O(N^2*K)\n",
    "        # space complexity: O(N*K)\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i: int, k: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return i\n",
    "\n",
    "            min_attempts = float(\"inf\")\n",
    "            for j in range(1, i + 1):\n",
    "                # if egg is broken at j, it will be: dp[j][k] = dp[j-1][k-1] + 1\n",
    "                # if egg is not broken at j, it will be: dp[j][k] = dp[i-j][k] +1\n",
    "                broken = dp(j - 1, k - 1)\n",
    "                not_broken = dp(i - j, k)\n",
    "\n",
    "                # chose the worst case\n",
    "                current_attempts = 1 + max(broken, not_broken)\n",
    "                min_attempts = min(min_attempts, current_attempts)\n",
    "\n",
    "            return min_attempts\n",
    "\n",
    "        return dp(n, 2)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
